Extended Distributed Learning Automata:A New Method for Solving Stochastic Graph Optimization Problems

摘要

In this paper, a new structure of cooperative learning automata so-calledextended learning automata (eDLA) is introduced. Based on the proposedstructure, a new iterative randomized heuristic algorithm for finding optimalsub-graph in a stochastic edge-weighted graph through sampling is proposed. Ithas been shown that the proposed algorithm based on new networked-structure canbe to solve the optimization problems on stochastic graph through less numberof sampling in compare to standard sampling. Stochastic graphs are graphs inwhich the edges have an unknown distribution probability weights. Proposedalgorithm uses an eDLA to find a policy that leads to an induced sub-graph thatsatisfies some restrictions such as minimum or maximum weight (length). At eachstage of the proposed algorithm, eDLA determines which edges to be sampled.This eDLA-based proposed sampling method may result in decreasing unnecessarysamples and hence decreasing the time that algorithm requires for finding theoptimal sub-graph. It has been shown that proposed method converge to optimalsolution, furthermore the probability of this convergence can be madearbitrarily close to 1 by using a sufficiently small learning rate. A newvariance-aware threshold value was proposed that can be improving significantlyconvergence rate of the proposed eDLA-based algorithm. It has been shown thatthe proposed algorithm is competitive in terms of the quality of the solution